package com.leetcode.algorithm.y22.m08.w2;

/**
 * 673. 最长递增子序列的个数
 * 
 * https://leetcode.cn/problems/number-of-longest-increasing-subsequence/
 * 
 * @author jie.deng
 *
 */
class Question0673Solution01 {

	public int findNumberOfLIS(int[] nums) {
		// DP状态定义
		// dpLIS[i]表示nums[0...i]以nums[i]结尾最长递增子序列的长度
		// dpLISCnt[i]表示nums[0...i]以nums[i]结尾最长递增子序列的个数
		int[] dpLIS = new int[nums.length];
		int[] dpLISCnt = new int[nums.length];

		// DP状态初始化
		dpLIS[0] = 1;
		dpLISCnt[0] = 1;

		// DP状态转移
		for (int i = 1; i < dpLIS.length; i++) {
			dpLIS[i] = 1;
			dpLISCnt[i] = 1;
			for (int j = 0; j < i; j++) {
				if (nums[i] > nums[j]) {
					if (dpLIS[j] + 1 == dpLIS[i]) {
						dpLISCnt[i] += dpLISCnt[j];
					} else if (dpLIS[j] + 1 > dpLIS[i]) {
						dpLIS[i] = dpLIS[j] + 1;
						dpLISCnt[i] = dpLISCnt[j];
					}
				}
			}
		}
		int maxLIS = dpLIS[0];
		int maxLISCnt = dpLISCnt[0];
		for (int i = 1; i < dpLIS.length; i++) {
			if (dpLIS[i] > maxLIS) {
				maxLIS = dpLIS[i];
				maxLISCnt = dpLISCnt[i];
			} else if (dpLIS[i] == maxLIS) {
				maxLISCnt += dpLISCnt[i];
			}
		}
		return maxLISCnt;
	}

}